#include <cstring>
#include <vector>
class Solution {
    int n;
    set<string> s;
    string path;
    bool vis[15];
public:
    void dfs(string str, int step)
    {
        if (step == n)
        {
            s.insert(path);
            return;
        }

        for (int i = 0; i < n; i++)
        {
            if (!vis[i])
            {
                vis[i] = true;
                path[step] = str[i];
                dfs(str, step + 1);
                vis[i] = false;
            }
        }
    }

    vector<string> Permutation(string str) {
        n = str.size();
        path.resize(n);
        memset(vis, false, sizeof vis);
        dfs(str, 0);

        return vector<string>(s.begin(), s.end());
    }
};